{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "算法作业 06\n",
    "========"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    " - 姓名：\t芮志清 \n",
    " - 学号：\t2018Z8020661080\n",
    " - 班级：\t人工智能学院2018级非全日制8班\n",
    " - 邮箱：\truizhiqing18@mails.ucas.ac.cn"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "设计时间复杂度为$O(n)$动态规划算法求解多米诺骨牌问题\n",
    "====\n",
    "\n",
    "# 算法设计:\n",
    "  从前向后依次加入骨牌，当加入第i+1个骨牌时，根据第i个骨牌不同状态的最优解，分别计算第i+1个骨牌不同状态的最优解，并记录下来。  \n",
    " - 问题分割: \n",
    "  - 子问题 $(s,i)$: 当第i个骨牌状态为s时，求$Card[1...n]$的最大解\n",
    "  - 用数组$M[2,n]$记录问题结果,M[s,i]表示状态为s时, $Card[1...n]$的最大解\n",
    " - 递推方程:  \n",
    "  设第$i$块骨牌$cards_i$的左右为$L_i$,$R_i$,则:  \n",
    "  $$M[0,1]=M[1,1]=0$$\n",
    "  $$M[0,i+1]=\\max{(M[0,i]+R_i*L_(i+1)),(M[1,i]+L_i*L_(i+1))}$$\n",
    "  $$M[1,i+1]=\\max{(M[0,i]+R_i*R_(i+1)),(M[1,i]+L_i*R_(i+1))}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from collections import namedtuple\n",
    "Card=namedtuple(\"Card\",[\"L\",\"R\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "sample=[(5,8),(4,2),(9,6),(7,7),(3,9),(11,10)] \n",
    "Cards=[Card(*_) for _ in sample]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "# 算法实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def dominoSumDN(cards):\n",
    "    \"\"\"\n",
    "    使用动态规划解决多米诺骨牌问题\n",
    "    返回 取得最大值时的骨牌列表和最大值\n",
    "    \"\"\"\n",
    "    cards=cards.copy() # cards 为输入参数\n",
    "    n=len(cards) # 骨牌数量\n",
    "    M=np.zeros((2,n)) # 记忆加和状态\n",
    "    P=np.zeros((2,n)) # 记忆上一步的位置状态\n",
    "    W=np.zeros((n)) # 骨牌的状态值 0表示R<L ,1表示R>=L\n",
    "    for index,card in enumerate(cards): # 为了方便状态表示，调整所有卡中左右的顺序为左边小于右边\n",
    "        cards[index]=Card(min(card),max(card)) # set card in status 0 : (R<=L) \n",
    "    for i in range(n-1): \n",
    "        # rl,ll,rr,lr 四个变量，分别表示当使用第i张骨牌的R或L与第i+1张骨牌的R或L配对时的乘积和\n",
    "        # \n",
    "        rl=M[0,i] + cards[i].R*cards[i+1].L\n",
    "        ll=M[1,i] + cards[i].R*cards[i+1].L\n",
    "        (M[0,i+1],P[0,i+1])=(rl,0) if (rl>ll) else (ll,1) # 记忆当i+1为状态0时的最佳情况\n",
    "        rr=M[0,i] + cards[i].R*cards[i+1].R\n",
    "        lr=M[1,i] + cards[i].R*cards[i+1].R\n",
    "        (M[1,i+1],P[1,i+1])=(rr,0) if (rr>lr) else (lr,1) # 记忆当i+1 为状态1时的最佳情况\n",
    "    \n",
    "    (Max,W[n-1] )=(M[0,n-1],0 )if M[0,n-1] > M[1,n-1] else (M[1,n-1],1) # 对两条分支进行合并，得到最大值\n",
    "\n",
    "    for i in range(n-1,0,-1): # 向前递推得到取得最大情况的状态值\n",
    "        W[i-1]= P[0,i] if W[i]==0 else P[1,i]\n",
    "        \n",
    "    for index in range(len(cards)): # 使用状态对骨牌做出变更\n",
    "        if W[index]==1:\n",
    "            cards[index]=Card(*cards[index][::-1])\n",
    "    return cards,Max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([Card(L=8, R=5),\n",
       "  Card(L=4, R=2),\n",
       "  Card(L=9, R=6),\n",
       "  Card(L=7, R=7),\n",
       "  Card(L=9, R=3),\n",
       "  Card(L=11, R=10)],\n",
       " 293.0)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dominoSumDN(cards=Cards)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 时间测试"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## $10^3$级"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4.63 ms ± 50.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "d=np.random.random((10**3,2))\n",
    "Cards=[Card(d[_,0],d[_,1]) for _ in range(np.shape(d)[0])]\n",
    "%timeit dominoSumDN(Cards)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## $10^4$级"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "47 ms ± 387 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "d=np.random.random((10**4,2))\n",
    "Cards=[Card(d[_,0],d[_,1]) for _ in range(np.shape(d)[0])]\n",
    "%timeit dominoSumDN(Cards)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## $10^6$级"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4.8 s ± 131 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "d=np.random.random((10**6,2))\n",
    "Cards=[Card(d[_,0],d[_,1]) for _ in range(np.shape(d)[0])]\n",
    "%timeit dominoSumDN(Cards)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 测试结果\n",
    "可以看出随数据量增加，消耗时间呈线性增加"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    ">>\n",
    "参考:\n",
    "1. [\"多米诺骨牌\"问题的动态规划算法](https://blog.csdn.net/duguduchong/article/details/6004451)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [conda env:math]",
   "language": "python",
   "name": "conda-env-math-py"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
